package mao.algorithm.sort;

/**
 * @author Totoro
 * @date 2020/7/10
 * @explain:
 */
public class MergeSort {

    private static void mergeSort(int[] data) {
        int[] temp = new int[data.length];
        mergeSort(data,temp,0,data.length);
    }

    private static void mergeSort(int[] data,int[] temp, int start, int end) {
        //递归结束的条件。
        if(start >= end-1) return;
        int middle = (end+start)/2;
        mergeSort(data,temp,start,middle);
        mergeSort(data,temp,middle,end);
        merge(data,start,middle,end);
    }
    private static void merge(int[] data, int start, int middle, int end) {
        int[] tempData = new int[end-start];
        int tempStart=start;
        int temp2Start=middle;
        int index=0;
        while((tempStart != middle) && (temp2Start != end)){
            if(data[tempStart]<data[temp2Start]){
                tempData[index] = data[tempStart];
                tempStart++;
            }else{
                tempData[index] = data[temp2Start];
                temp2Start++;
            }
            index++;
        }
        while((tempStart != middle)){
            tempData[index] = data[tempStart];
            tempStart++;
            index++;
        }

        while((temp2Start != end)){
            tempData[index] = data[temp2Start];
            temp2Start++;
            index++;
        }
        for (int i=start ;i<end;i++) {
            data[i]=tempData[i-start];
        }
    }
}

